Поиск с восхождением к вершине иногда называют жадным локальным поиском, поскольку в процессе его выполнения происходит захват самого хорошего соседнего состояния без предварительных рассуждений о том, куда следует отправиться дальше. Жадность считается одним из семи смертных грехов, но, как оказалось, жадные алгоритмы часто показывают весьма высокую производительность. Во время поиска с восхождением к вершине зачастую происходит очень быстрое продвижение в направлении к решению, поскольку обычно бывает чрезвычайно легко улучшить плохое состояние. Например, из состояния, показанного на рис. 4.8, a, достаточно сделать лишь пять ходов, чтобы достичь состояния, показанного на рис. 4.8, б, которое имеет оценку h=l и очень близко к одному из решений.

Рис. 4.8. Пример применения алгоритма с восхождением к вершине: диаграмма состояния задачи с восемью ферзями, характеризующегося эвристической оценкой стоимости Ъ=17; на этой диаграмме показано значение h для каждого возможного преемника, полученное путем передвижения ферзя в пределах своего столбца; отмечены наилучшие ходы (а); локальный минимум в пространстве состояний задачи с восемью ферзями; это состояние имеет оценку Ъ=1, но каждый преемник характеризуется более высокой стоимостью (б)

К сожалению, поиск с восхождением к вершине часто заходит в тупик по описанным ниже причинам.

•   Локальные максимумы. Локальный максимум представляет собой пик, более высокий по сравнению с каждым из его соседних состояний, но более низкий, чем глобальный максимум. Алгоритмы с восхождением к вершине, которые достигают окрестностей локального максимума, обеспечивают продвижение вверх, к этому пику, но после этого заходят в тупик, из которого больше некуда двигаться. Такая проблема схематически показана на рис. 4.7. Более конкретный пример состоит в том, что состояние, показанное на рис. 4.8, б, фактически представляет собой локальный максимум (т.е. локальный минимум для оценки стоимости h) задача еще не решена, а при любом передвижении отдельно взятого ферзя ситуация становится еще хуже.

•    Хребты. Пример хребта показан на рис. 4.9. При наличии хребтов возникают последовательности локальных максимумов, задача прохождения которых для жадных алгоритмов является очень трудной.

•    Плато. Это область в ландшафте пространства состояний, в которой функция оценки является плоской. Оно может представлять собой плоский локальный максимум, из которого не существует выхода вверх, или уступ, из которого возможно дальнейшее успешное продвижение (см. рис. 4.7). Поиск с восхождением к вершине может оказаться неспособным выйти за пределы плато.